package com.dbh.alg.algorithm.hot100.栈;


import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 示例 2：
 *
 *
 *
 * 输入： heights = [2,4]
 * 输出： 4
 *
 *
 * 提示：
 *
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 */
public class Leetcode84_柱状图中最大的矩形 {

    public int largestRectangleArea(int[] heights) {
        // 获取原始数组长度
        int n = heights.length;
        // 创建一个新数组，长度为原始数组+2 (用于添加左右边界)
        int[] newHeights = new int[n + 2];
        // 复制原始数组到新数组中间位置
        System.arraycopy(heights, 0, newHeights, 1, n);
        // 设置左边界为0
        newHeights[0] = 0;
        // 设置右边界为0
        newHeights[n + 1] = 0;

        // 使用栈存储柱子的索引 (栈中索引对应的柱子高度将保持单调递增)
        Deque<Integer> stack = new LinkedList<>();
        // 初始化最大面积
        int maxArea = 0;

        // 遍历新数组 (包含边界)
        for (int i = 0; i < newHeights.length; i++) {
            // 当前柱子高度小于栈顶柱子高度时 (破坏递增)
            while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                // 弹出栈顶索引，并获取该柱子的高度
                int height = newHeights[stack.pop()];
                // 计算宽度：当前索引-新栈顶索引-1
                // 新栈顶索引是左边第一个比弹出柱子矮的位置
                // 当前索引i是右边第一个比弹出柱子矮的位置
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }

}
